1. Field of the Invention
Generally, the present invention relates to the telecommunications and digital networking. More specifically, the present invention relates to the deallocation of memory in a multicasting network environment.
2. Description of the Related Art
In the realm of digital networking and telecommunications, data is often assembled and then transmitted and received in discrete units known as packets. Packets originating from the same source device, connection or application and terminating at the same destination devices, connections or applications can be grouped together in a “flow.” Thus, a flow comprises one or more packets. Though the term “packets” is used in this discussion to define a flow, “packets” may also refer to other discrete data units, such as frames and the like. Network devices (e.g. switches, routers, etc.) that intercept and forward such flows are often configured with a plurality of ingress ports (i.e., ports into which “input” flows are received at the device) and a plurality of egress ports (i.e., ports from which “output” flows or packets are sent or routed away from the device). In this regard, and for purposes of discussion, ports may be physical, logical or a combination of physical and logical. When an input flow is received by a network device at an ingress port, it could be destined for output over one or more egress ports. An input flow destined for output over only one egress port is referred to as unicast (or a unicast flow), while an input flow with some integer number, n, of egress port destinations is referred to as multicast (or a multicast flow). In this way, a unicast flow can simply be considered as a multicast flow with n=1 destination egress ports.
The typical and most straightforward way of achieving multicasting is to request, and have resent, the multicast flow from the original source (i.e., the original source sends the input flow to the ingress ports of the network device) as many times as needed for subsequent transmission to each designated egress port. For numerous reasons apparent to those skilled in the art, however, such a straightforward multicasting mechanism is time-inefficient and consumes excessive amounts of network bandwidth.
FIG. 1 illustrates a more common approach to achieve multicasting for an input flow by performing data replication at the multicast point. As shown in FIG. 1, the packets of the input flow 110 are written to a memory device 100 such as a RAM (Random Access Memory). The memory device 100 captures the packets of the input flow 110 and stores them until all egress ports for which that flow is designated have read each packet. In the example shown, the input flow 110 is destined for four multicast “members” (i.e., those egress ports for which the flow is designated and destined) A, B, C and D. There may be more total egress ports within a network device than multicast members for a given input flow. The stored packet 110 is then read out from the memory device 100 as needed to fulfill the multicast requirement, which in this example is four times. This approach, called “replication,” prevents the input packet or flow from having to be retransmitted from its original source multiple times, thereby improving efficiency.
However, since memory device 100 has a limited storage capacity, the memory device can become full of packets and unable to accept any more packet traffic. Also, after a packet of the multicast flow has been transmitted to all of its multicast destinations, it is no longer needed. For these reasons, a memory deallocation procedure is often applied to the memory device using a memory controller or other similar mechanism. In this way, the memory device can be freed from data that is no longer needed. The deallocation procedure must be able to recognize when the multicast input packet has been passed to all of its members.
Traditional deallocation procedures use a counter that first initializes to the number of designated multicast recipients (e.g., some or all of the egress ports on the network device) and then decrements each time the memory is accessed by a multicast member. However, such a deallocation technique does not perform well when the number of multicast input flows is very large (e.g., into the thousands or more), since a counter must be set and maintained for each input packet. Further, the counters and counter manipulation are typically handled outside of the input flow memory device itself, for example, in a memory controller or other external device. Thus, the memory controller adds excessive delay to the entire memory reading egress process.
Often, during the traditional deallocation procedure, each multicast member must signal to the counter (i.e., the memory controller) that it has finished reading the last packet of the input flow from the memory device. Thus, not only must the counter be accessible by every multicast member, it must be updatable by each member. Since a given packet of an input flow can only be read by one member at a time, this counter access/update creates one or more extra wait states that negatively affect multicasting performance. This means that the counter is locked by each multicast recipient and cannot be updated by subsequent recipients until that preceding recipient has finished. This problem is exacerbated where the multicast consists of a very large number of packets in the input flow. Further, it is possible that each of the multicast members may read out the flow at different rates of speed. Further still, where multicast members do not update in a synchronous fashion at even speeds, the counter can yield invalid results.
Thus, it would be advantageous to have a memory deallocation technique that overcomes these and other limitations and is scalable for very large numbers of flows existing within a single network device.